﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BIG = System.Numerics.BigInteger;

namespace PodpisyElektorniczne.Classes
{
    /// <summary>
    /// here is some naive implementation of factorization 
    /// another prime number on the basis of another integer big number
    /// this factorization is based on Fermat's decomposition method
    /// </summary>
    
    public class FactorizationFactory
    {
        public FactorizeData Orders { get; protected set; }

        public FactorizationFactory()
        {
            //Orders = new FactorizeData();
        }
        /// <summary>
        /// I will probably use some big prime used in user key factorization
        /// </summary>
        public FactorizeData FermatFactor(BIG p, out BIG remind)
        {
            var q = new BIG();
            var reminder = new BIG(-1);
            remind = reminder;
            var a = FactorizationFactory.sqrt(p, out reminder);
            if(reminder!=0) return default(FactorizeData); //get another number
            
            var b2 = a*a - p;
            sqrt(b2, out reminder);
            while(reminder!=0)
            {
                a++;
                b2 = a*a - p;
                q = sqrt(b2, out reminder);
            }
            Orders = new FactorizeData(p,q);
            return Orders;
        }

        /// <summary>
        /// Procedure which compute square number of given Big Integer.
        /// Remmber: res*res + reminder = x - this is key information here
        /// </summary>
        /// <param name="x">compute sqrt of it</param>
        /// <param name="reminder">reminder</param>
        /// <returns>
        /// res: sqrt number or the closest number to the real squer plus remian of the operation
        /// </returns>
        public static BIG sqrt(BIG x, out BIG reminder)//res * res + rem = x
        {
            var res = new BIG();
            var bit = new BIG(1) << 14;

            for (bit = 4; bit < x; bit <<= 2) ; //4*bit>x
            for (res = 0; bit != 0; bit >>= 2)
                if (res + bit <= x) 
                { 
                    x -= res + bit; 
                    res = (res >> 1) + bit; 
                }
                else res >>= 1;
            reminder = x;
            return res;
        }

    }
}
